The common sense suggests that networks are not random mazes of purposelessconnections, but that these connections are organised so that networks canperform their functions well. One function common to many networks is targetedtransport or navigation. Using game theory, here we show that minimalisticnetworks designed to maximise the navigation efficiency at minimal cost sharebasic structural properties with real networks. These idealistic networks areNash equilibria of a network construction game whose purpose is to find anoptimal trade-off between the network cost and navigability. We show that theseskeletons are present in the Internet, metabolic, English word, US airport,Hungarian road networks, and in a structural network of the human brain. Theknowledge of these skeletons allows one to identify the minimal number of edgesby altering which one can efficiently improve or paralyse navigation in thenetwork.
展开▼
